#include<stdio.h>
#include<malloc.h>

int n;
struct VNode{
    int position;
    struct VNode* next;
};

struct ArcNode{
    int mark;
    struct VNode* first;
};

void DFS(struct ArcNode* v,struct ArcNode* w){
    struct VNode* L;
    w->mark=1;
    L=w->first;
    while(L!=NULL){
        if((v+(L->position))->mark==0){      
            DFS(v,(v+L->position));
        }
        L=L->next;
    }
}

int main(){
    int i,j,k;
    int key1,key2;
    int num=0;
    struct ArcNode* p;
    struct VNode* temp;
    struct VNode* flag;
    printf("该有向图有多少个顶点：\n");
    scanf("%d",&n);
    while(n<1){
        printf("你输入的值不合理，请重新输入：\n");
        scanf("%d",&n);
    }
    p=(struct ArcNode*)malloc(n*sizeof(struct ArcNode));      
    for(i=0;i<n;i++){
        printf("请输入以V%d为弧尾的所有弧，并以-1结束输入\n",i+1);
        scanf("%d",&k);        
        if(k==-1){
            p[i].mark=0;
            p[i].first=NULL;
        }else{
            temp=(struct VNode*)malloc(sizeof(struct VNode));
            temp->position=k;
            temp->next=NULL;
            p[i].first=temp;
            p[i].mark=0;
            flag=temp;                   
            scanf("%d",&k);
            while(k!=-1){
                temp=(struct VNode*)malloc(sizeof(struct VNode));
                temp->position=k;
                temp->next=NULL;
                flag->next=temp;
                flag=temp;
                scanf("%d",&k);
            }
        }           
    }
    printf("请输入要判断的两顶点的位置：\n");
    printf("如果想判断V1和V2是否连通，则输入0 1\n");
    scanf("%d%d",&key1,&key2);
    DFS(p,(p+key1));
    if(p[key2].mark==1){
        printf("这两个点连通！\n",key1+1,key2+1);
    }else{
        p[key1].mark=0;
        DFS(p,(p+key2));
        if(p[key1].mark==1){
            printf("这两个点连通！\n",key1+1,key2+1);
        }else{
            printf("这两个点不连通！\n",key1+1,key2+1);
        }
    }
    return 0;    
}
